This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
A fundamental operation in public-key cryptography is modular exponentiation. On input N, x and d, y=xd mod N is computed. There are, naturally, a host of prior art modular exponentiation algorithms, two examples of which being given hereinafter.
Algorithm 1 - Left-to-right binary methodInput: N, x ε   /N   and d = (dl−1, ..., d0)2 ε  Output: y = xd mod N   1: R[0] ← 1 ; R[1] ← x   2: for j = l−1 down to 0 do   3:  R[0] ← R[0]2 mod N   4:  if (dj ≠ 0) then R[0] ← R[0] · R[1] mod N   5: end for   6: return R[0]
Algorithm 2 - Right-to-left binary methodInput: N, x ε   /N   and d = (dl−1, ..., d0)2 ε  Output: y = xd mod N   1: R[0] ← 1 ; R[1] ← x   2: for j = 0 to l−1 do   3:  if (dj ≠ 0) then R[0] ← R[0] · R[1] mod N   4:  R[1] ← R[1]2 mod N   5: end for   6: return R[0]
While both methods are efficient, the skilled person will appreciate that they may be subject to side-channel, specifically Simple Power Analysis (SPA) attacks. See “Paul Kocher, Joshua Jaffe, and Benjamin Jun; Differential Power Analysis; In M. Wiener, editor, Advances in Cryptology—CRYPTO'99, volume 1666 of Lecture Notes in Computer Science, pages 388-397; Springer-Verlag, 1999”; and “Paul C. Kocher; Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems; In N. Koblitz, editor, Advances in Cryptology—CRYPTO'96, volume 1109 of Lecture Notes in Computer Science, pages 104-113. Springer-Verlag, 1996”.
The main problem resides in the presence of the conditional branch, i.e. the ‘if’ statement.
One way to overcome this problem is to execute a multiplication in every loop of the round, in other words perform a fake multiplication whenever dj=0. See “Jean-Sébastien Coron; Resistance Against Differential Power Analysis for Elliptic Curve Cryptosystems; In C. K. Koc and C. Paar, editors, Cryptographic Hardware and Embedded Systems—CHES'99, volume 1717 of Lecture Notes in Computer Science, pages 292-302. Springer-Verlag, 1999”. The resulting implementations are however slower; the cost increases from around 1.5 multiplications per bit to 2 multiplications per bit. An added drawback is that the implementations become vulnerable to safe-error attacks; see “Sung-Ming Yen and Marc Joye; Checking before output may not be enough against fault-based cryptanalysis; IEEE Transactions on Computers, 49(9):967-970, 2000”; and “Sung-Ming Yen, Seung-Joo Kim, Seon-Gan Lim, and Sang-Jae Moon; A Countermeasure Against One Physical Cryptanalysis May Benefit Another Attack; In K. Kim, editor, Information Security and Cryptology—ICISC 2001, volume 2288 of Lecture Notes in Computer Science, pages 417-427. Springer-Verlag, 2002”.
A better way to prevent SPA-type attacks is to use so-called side-channel atomicity; see “Benoît Chevallier-Mames, Mathieu Ciet, and Marc Joye; Low-Cost Solutions for Preventing Simple Side-channel Analysis: Side-Channel Atomicity; IEEE Transactions on Computers, 53(6):760-768, 2004”. The corresponding algorithms are:
Algorithm 3 - Left-to-right binary method (atomic)Input: N, x ε   /N   and d = (dl−1, ..., d0)2 ε  Output: y = xd mod N   1: R[0] ← 1 ; R[1] ← x   2: j ← l−1 ; b ← 0   3: while (j ≧ 0) do   4:  R[0] ← R[0] · R[b] mod N   5:  b ← b ⊕ dj; j ← j −   b   6: end while   7: return R[0]
Algorithm 4 - Right-to-left binary method (atomic)Input: N, x ε   /N   and d = (dl−1, ..., d0)2 ε  Output: y = xd mod N   1: R[0] ← 1 ; R[1] ← x   2: j ← 0; b ← 1   3: while (j ≦ l−1) do   4:  b ← b ⊕ dj   5:  R[b] ← R[b] · R[1] mod N; j ← j + b   6: end while   7: return R[0]
In Algorithms 3 and 4, ⊕ denotes the XOR (exclusive OR) operator and  denotes the negation operator (i.e., if b=0 then b=1 and if b=1 then b=0).
It will be appreciated that the cost is not increased, but remains at around 1.5 multiplications per bit. It will further be appreciated that side-channel atomicity is not restricted to the binary exponentiation methods. Further algorithms may be found in the aforementioned paper by Chevallier-Mames, Ciet and Joye.
While side-channel atomicity leads to very nice algorithms, it should be stressed that the methodology assumes that the multiplication operation is atomic. More explicitly, it assumes that it is not possible to make the distinction between a modular squaring and a modular multiplication by observing a suitable side channel. This assumption is not always fulfilled. Concrete attacks are reported in “Frédéric Amiel, Benoît Feix, Michael Tunstall, Claire Whelan, and William P. Marnane; Distinguishing Multiplications from Squaring Operations; In R. Avanzi, L. Keliher, and F. Sica, editors, Selected Areas in Cryptography—SAC 2008, volume 5394 of Lecture Notes in Computer Science, pages 346-360. Springer-Verlag, 2009”.
It will thus be appreciated that there is a need for a solution in which a modular multiplication, from a side-channel viewpoint, behaves like a modular squaring. This invention provides such a solution.